package com.lw.leetcode.arr.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1234. 替换子串得到平衡字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/19 16:46
 */
public class BalancedString {

    public static void main(String[] args) {
        BalancedString test = new BalancedString();

        // 0
        String str = "QWER";

        // 1
//        String str = "QQWE";

        // 2
//        String str = "QQQW";

        // 3
//        String str = "QQQQ";

        // 2
//        String str = "WQQQ";

        // 3
//        String str = "WQWRQQQW";

        int i = test.balancedString(str);
        System.out.println(i);
    }

    // Q', 'W', 'E', 'R'
    public int balancedString(String s) {
        int[] arr = new int[4];
        Map<Character, Integer> map = new HashMap<>();
        map.put('Q', 0);
        map.put('W', 1);
        map.put('E', 2);
        map.put('R', 3);
        char[] chars = s.toCharArray();
        int length = s.length();
        for (char aChar : chars) {
            arr[map.get(aChar)]++;
        }
        int l = length >> 2;
        for (int i = 0; i < 4; i++) {
            arr[i] -= l;
        }
        if (arr[0] == 0 && arr[1] == 0 && arr[2] == 0) {
            return 0;
        }
        int st = 0;
        int end = 0;
        int min = Integer.MAX_VALUE;
        while (end < length) {
            arr[map.get(chars[end++])]--;
            if (find(arr)) {
                while (st <= end) {
                    min = Math.min(min, end - st);
                    arr[map.get(chars[st++])]++;
                    if (!find(arr)) {
                        break;
                    }
                }
            }
        }
        return min;
    }

    private boolean find(int[] arr) {
        for (int i : arr) {
            if (i > 0) {
                return false;
            }
        }
        return true;
    }

}
